
/*
 * Conjunto de funciones que proveen una especificación completa de trabajo que será usada por el coordinador
 * y repartida a los nodos que corresponda.
 */

#include <math.h>
#include <malloc.h>
#include <string.h>

#include "plan-trabajo.h"

#include "../varios/log.h"
#include "../varios/mensajes.h"

#include "../../compartido/vectores.h"


enum ACCION_NODO {NINGUNA, ENVIAR, RECIBIR, TERMINADO};

struct NODO_MATRIZ {
    enum ACCION_NODO accion;    // Acción a llevar a cabo en el nodo
    long long tamanio;                // Tamaño del vector en el nodo
    int idNodo;               // Nodo destino u originen al que el nodo debería enviar o recibir
};


long long *calcularTamVectoresFinales(int *finales, struct NODO_MATRIZ *estadoFinal);
int *establecerNodosFinales(int *activos, int cantNodos);
long long *calcularCantidadDePartesPorNodo(int cantNodos, long long cantTotalPartes);
long long *calcularCantidadElementosPorNodo(int cantNodos, long long *cantPartesPorNodo, long long tamVector, long long cantTotalPartes);
long long calcularCantidadTotalDePartes(int cantNodos);
struct NODO_MATRIZ *fase1(int cantNodos, long long *cantPartesPorNodo, long long *cantElemPorNodo, int *activos);
int contarActivos(int *activos, int cantNodos);
int indiceActivoPar(int *activos, int indiceBase, int cantidad);
int activoPosterior(int *activos, int indiceBase);
int activoAnterior(int *activos, int indiceBase);
struct ASIGNACION_NODO *construirAsignacion(int indice, struct NODO_MATRIZ **matriz, long long cantElemNodo, int cantNodos);
char *imprimirMatriz(struct NODO_MATRIZ **matriz, int hastaIndice, int cantidad);
char *imprimirNodoMatriz(struct NODO_MATRIZ *nodo);


/*
 *Implementación de función definida en cabecera.
 */
struct ESPEC_TRABAJO_COORD obtenerPlanTrabajo(int cantNodos, long long tamVector) {
    
    // TODO - Manejar el caso en que hay mas nodos que elementos en el vector
    // TODO - Manejar el caso en el que algunos nodos quedan sin trabajo
    
    LOGGER("Nos piden el plan de trabajo para %d nodos con un vector de %l elementos", cantNodos, tamVector);
    
    // Obtenemos la cantidad de partes que recibirá cada nodo y cuantos elementos recibirá cada nodo
    long long cantTotalPartes = calcularCantidadTotalDePartes(cantNodos);
    long long *cantPartesPorNodo = calcularCantidadDePartesPorNodo(cantNodos, cantTotalPartes);
    long long *cantElemPorNodo = calcularCantidadElementosPorNodo(cantNodos, cantPartesPorNodo, tamVector, cantTotalPartes);
    LOGGER("Cantidad total de partes = %l", cantTotalPartes);
    LOGGER("Cantidad de partes por nodo = %s", imprimirBloqueLong(cantPartesPorNodo, cantNodos));
    LOGGER("Cantidad elementos por nodo = %s", imprimirBloqueLong(cantElemPorNodo, cantNodos));
    
    
    /**
     * Determinamos el esquema de envío de los vectores entre los nodos (Son 3 fases)
     * 
     * Fase 1: Necesitamos que la cantidad de nodos activos sea par
     */
    
    // Creamos la matriz de procesamiento
    int cantNiveles = (int) floor(log2(cantNodos));
    if (cantTotalPartes != cantNodos || cantNodos == 2) {
        cantNiveles++;
    }
    LOGGER("Cantidad de niveles %d", cantNiveles);
    struct NODO_MATRIZ **matriz = malloc(sizeof(struct NODO_MATRIZ *) * cantNiveles);
    
    int *activos = malloc(sizeof(int) * cantNodos); // Bandera por nodo que indica si esta activo o no
    int nivelActual = 0; // Referencia al nivel actual de procesamiento que se esta determinando
    
    // Ejecutamos las fases 1 solo si la cantidad de nodos es mayor que 2
    matriz[nivelActual] = fase1(cantNodos, cantPartesPorNodo, cantElemPorNodo, activos);
    LOGGER("Matriz de fase 1: %s", imprimirMatriz(matriz, 0, cantNodos));
    nivelActual++;
    
    /*
     * Fase 2. Reduccion hasta llegar a solo 2 nodos
     */
    int cantActivos = contarActivos(activos, cantNodos);
    
    while (cantActivos>2) {
        int *nuevosActivos = malloc(sizeof(int) * cantNodos);
        matriz[nivelActual] = malloc(sizeof(struct NODO_MATRIZ) * cantNodos);
        int u;
        for (u=0; u<cantNodos; u++) {
            if (activos[u]==0) {
                matriz[nivelActual][u].accion = TERMINADO;
                nuevosActivos[u] = 0;
            } else {
                if (indiceActivoPar(activos, u, cantNodos)) {
                    nuevosActivos[u] = 0;
                    matriz[nivelActual][u].accion = ENVIAR;
                    matriz[nivelActual][u].idNodo = activoPosterior(activos, u);
                    matriz[nivelActual][u].tamanio = matriz[nivelActual-1][u].tamanio;
                } else {
                    nuevosActivos[u] = 1;
                    matriz[nivelActual][u].accion = RECIBIR;
                    int indiceActivoAnterior = activoAnterior(activos, u);
                    matriz[nivelActual][u].idNodo = indiceActivoAnterior;
                    matriz[nivelActual][u].tamanio = matriz[nivelActual-1][u].tamanio
                            + matriz[nivelActual][indiceActivoAnterior].tamanio;
                }
            }
        }
        
        LOGGER("Matriz de nivel %d: %s", nivelActual, imprimirMatriz(matriz, nivelActual, cantNodos));
        
        free(activos);
        activos = nuevosActivos;
        cantActivos = cantActivos / 2;
        nivelActual++;
        
    }
    
    /*
     * Fase 3. Envio de los nodos finales al coordinado
     */
    matriz[nivelActual] = malloc(sizeof(struct NODO_MATRIZ) * cantNodos);
    int e;
    for (e=0; e<cantNodos; e++) {
        if (activos[e]==1) {
            matriz[nivelActual][e].accion = ENVIAR;
            matriz[nivelActual][e].idNodo = -1;
            matriz[nivelActual][e].tamanio = matriz[nivelActual-1][e].tamanio;
        } else {
            matriz[nivelActual][e].accion = TERMINADO;
        }
    }
    
    LOGGER("Matriz de fase 3: %s", imprimirMatriz(matriz, nivelActual, cantNodos));

    
    /*
     * Convertimos la matriz de procesamiento en asignaciones 
     */
    
    // Estructura que retornaremos luego. La inicializamos.
    struct ESPEC_TRABAJO_COORD espec;
    espec.asignaciones = malloc(sizeof(struct ASIGNACION_NODO *) * cantNodos);
    
    // Realizamos la conversion para cada nodo
    int k;
    for (k=0; k<cantNodos; k++) {
        espec.asignaciones[k] = construirAsignacion(k, matriz, cantElemPorNodo[k], cantNodos);
    }
    
    // Calculamos el tamaño de los 2 ultimos vectores finales, y quienes los enviaran
    espec.nodosFinales = establecerNodosFinales(activos, cantNodos);
    espec.tamNodosFinales = calcularTamVectoresFinales(espec.nodosFinales, matriz[nivelActual]);

    // Liberamos memoria
    int u;
    for (u=0; u<cantNiveles; u++) {
        free(matriz[u]);
    }
    free(matriz);
    free(cantElemPorNodo);
    free(activos);
    free(cantPartesPorNodo);
    
    LOGGER("Fin de la creacion de la especificacion de trabajo");
    return espec;
    
}


/*
 * Determina el tamaño de los 2 ultimos vectores que serán enviados al coordinador
 */
long long *calcularTamVectoresFinales(int *finales, struct NODO_MATRIZ *estadoFinal) {
    long long *tams = malloc(sizeof(long long) * 2);
    tams[0] = estadoFinal[finales[0]-1].tamanio;
    tams[1] = estadoFinal[finales[1]-1].tamanio;
    return tams;
}


/*
 * Determina cuales son los 2 ultimos nodos que enviarán sus vectores al coordinador
 */
int *establecerNodosFinales(int *activos, int cantNodos) {
    int *finales = malloc(sizeof(int) * 2);
    int o;
    int indice = 0;
    for (o=0; o<cantNodos; o++) {
        if (activos[o]==1) {
            finales[indice] = o+1;
            indice++;
        }
    }
    return finales;
}


/*
 * Calcula la cantidad de partes que s ele enviará a cada nodo
 */
long long *calcularCantidadDePartesPorNodo(int cantNodos, long long cantTotalPartes) {
    
    // Calculamos la cantidad de nodos que recibirán 2 partes en vez de una
    long long cantidadPartesExtra = cantTotalPartes - cantNodos;
    
    // Calculamos la cantidad de elementos que recibirá cada nodo
    long long *cantPartesPorNodo = malloc(sizeof(long long) * cantNodos);
    int p;
    for (p=0; p<cantNodos; p++) {
        if (p<cantidadPartesExtra) {
            cantPartesPorNodo[p] = 2;
        } else {
            cantPartesPorNodo[p] = 1;
        }
    }
    
    return cantPartesPorNodo;
    
}


/*
 * Calcula la cantidad de elementos que se enviarán a cada nodo, teniendo en cuenta la cantidad de partes
 * que debe recibir cada uno.
 */
long long *calcularCantidadElementosPorNodo(int cantNodos, long long *cantPartesPorNodo, long long tamVector, long long cantTotalPartes) {
    
    // Calculamos el tamaño de cada parte
    long long tamParteBase = floor((double)tamVector / cantTotalPartes);
    long long cantPartesConElemExtra = tamVector % cantTotalPartes;
    long long *tamPartes = malloc(sizeof(long long) * cantTotalPartes);
    long long i;
    for (i=0; i<cantTotalPartes; i++) {
        if (i<cantPartesConElemExtra) {
            tamPartes[i] = tamParteBase + 1;
        } else {
            tamPartes[i] = tamParteBase;
        }
    }
    
    // Calculamos la cantidad de elementos que recibirá cada nodo
    long long *cantElemPorNodo = malloc(sizeof(long long) * cantNodos);
    int p;
    long long indiceTams = 0;
    for (p=0; p<cantNodos; p++) {
        if (cantPartesPorNodo[p] == 2) {
            cantElemPorNodo[p] = tamPartes[indiceTams] + tamPartes[indiceTams+1];
            indiceTams += 2;
        } else {
            cantElemPorNodo[p] = tamPartes[indiceTams];
            indiceTams++;
        }
    }
    
    free(tamPartes);
    
    return cantElemPorNodo;
    
}


/*
 * Calcula la cantidad de partes en la que se dividirá el vector, de acuerdo
 * a la cantidad de nodos que deben procesarlo.
 * La cantidad de partes es la menor potencia de 2 mayor que la cantidad de nodos.
 */
long long calcularCantidadTotalDePartes(int cantNodos) {
    int potencia = (int) ceil(log2(cantNodos));
    return (long long) pow(2, potencia);
}


struct NODO_MATRIZ *fase1(int cantNodos, long long *cantPartesPorNodo, long long *cantElemPorNodo, int *activos) {

    struct NODO_MATRIZ *nodos = malloc(sizeof(struct NODO_MATRIZ) * cantNodos);
    
    if (cantNodos == 2) {
        
        // No hace falta ejecutar el algoritmo. Solo seteamos lo necesario para que los 2 nodos sean vistos
        // como enviadores finales
        
        activos[0] = 1;
        nodos[0].accion = NINGUNA; // Colocamos esta accion para que la fase 3 lo levante como nodo final
        nodos[0].idNodo = 0;  // Este dato es ignorado luego
        nodos[0].tamanio = cantElemPorNodo[0];
        
        activos[1] = 1;
        nodos[1].accion = NINGUNA; // Colocamos esta accion para que la fase 3 lo levante como nodo final
        nodos[1].idNodo = 0;  // Este dato es ignorado luego
        nodos[1].tamanio = cantElemPorNodo[1];
        
    } else {
        
        int contadorDeSimples = 0;

        int l;
        for (l=0; l<cantNodos; l++) {
            struct NODO_MATRIZ nodo;
            if (cantPartesPorNodo[l] == 2) {
                activos[l] = 1;
                nodo.accion = NINGUNA;
                nodo.idNodo = -2;
                nodo.tamanio = cantElemPorNodo[l];
            } else {
                if (contadorDeSimples%2 == 0) { // es par
                    activos[l] = 0;
                    nodo.accion = ENVIAR;
                    nodo.idNodo = l+1;
                    nodo.tamanio = cantElemPorNodo[l];
                } else {
                    activos[l] = 1;
                    nodo.accion = RECIBIR;
                    nodo.idNodo = l-1;
                    nodo.tamanio = cantElemPorNodo[l] + cantElemPorNodo[l-1];
                }
                contadorDeSimples++;
            }
            nodos[l] = nodo;
        }
        
    }
    
    return nodos;
    
}


int contarActivos(int *activos, int cantNodos) {
    int cant = 0;
    int i;
    for (i=0; i< cantNodos; i++) {
        if (activos[i] == 1) {
            cant++;
        }
    }
    return cant;
}


int indiceActivoPar(int *activos, int indiceBase, int cantidad) {
    int i;
    int cantActivos = 0;
    for (i=indiceBase; i<cantidad; i++) {
        if (activos[i]==1) {
            cantActivos++;
        }
    }
    return cantActivos%2 == 0;
}


int activoPosterior(int *activos, int indiceBase) {
    int i=indiceBase+1;
    while(1) {
        if(activos[i]==1) {
            return i;
        }
        i++;
    }
    return -2;
}


int activoAnterior(int *activos, int indiceBase) {
    int i=indiceBase-1;
    while(1) {
        if(activos[i]==1) {
            return i;
        }
        i--;
    }
    return -2;
}


struct ASIGNACION_NODO *construirAsignacion(int indice, struct NODO_MATRIZ **matriz, long long cantElemNodo, int cantNodos) {
    
    LOGGER("Construimos asignacion del indice %d, cantElem: %l, cantNodos: %d", indice, cantElemNodo, cantNodos);
    
    /*
     * Determinamos como se le enviarán los vectores intermedios y el destino final.
     */
    long long *tamOrigInterm = malloc(sizeof(long long) * cantNodos);
    int *origenInterm = malloc(sizeof(int) * cantNodos);
    int cantOrigenInterm = 0;
    int destinoFinal = -1;
    
    int continuar = 1;
    int nivel = 0;
    
    while(continuar) {
        
        if (matriz[nivel][indice].accion == TERMINADO) {
            continuar = 0;
        } else if (matriz[nivel][indice].accion != NINGUNA) {
            if (matriz[nivel][indice].accion == ENVIAR) {
                destinoFinal = matriz[nivel][indice].idNodo + 1;
                continuar = 0;
            } else if (matriz[nivel][indice].accion == RECIBIR) {
                int indiceOrigen = matriz[nivel][indice].idNodo;
                origenInterm[cantOrigenInterm] = indiceOrigen + 1;
                tamOrigInterm[cantOrigenInterm] = matriz[nivel][indiceOrigen].tamanio;
                cantOrigenInterm++;
            }
        }
        LOGGER("Nivel %d", nivel);
        nivel++;
        
    }
    
    /*
     * Armamos y retornamos el asignacion final
     */
    LOGGER("Armamos el asignacion");
    struct ASIGNACION_NODO *asignacion = malloc(sizeof(struct ASIGNACION_NODO));
    asignacion->tamVectoresIntermedios = tamOrigInterm;
    asignacion->originesIntermedios = origenInterm;
    asignacion->cantOriginesIntermedios = cantOrigenInterm;
    asignacion->destinoFinal = destinoFinal;
    asignacion->tamVectorInicial = cantElemNodo;

    LOGGER("Asignacion construido: %s", imprimirAsignacion(asignacion));
    
    return asignacion;
    
}


/*
 * Implementacion de funcion definida en cabecera
 */
char *imprimirEspecTrabajoCoord(struct ESPEC_TRABAJO_COORD *datos, int cant) {
    
    char *vect1 = imprimirBloqueInt(datos->nodosFinales, 2);
    char *vect2 = imprimirBloqueLong(datos->tamNodosFinales, 2);
    char *vect3 = malloc(sizeof(char) * 1024 * 1024 * cant);
    vect3[0] = 0;
    
    char *buff;
    
    int o;
    for (o=0; o<cant; o++) {
        buff = imprimirAsignacion(datos->asignaciones[o]);
        strcat(vect3, buff);
        strcat(vect3, ",\n");
        free(buff);
    }
    
    char* impr = malloc(sizeof(char) * (1024*1024*cant+1024));
    impr[0] = 0;
    sprintf(impr, "ESPEC_TRABAJO_COORD = {asignaciones=%s,\n\tnodosFinales=%s,\n\ttamNodosFinales=%s\n}",
        vect3, vect1, vect2);
    
    free(vect1);
    free(vect2);
    free(vect3);
    
    return impr;
    
}


char *imprimirMatriz(struct NODO_MATRIZ **matriz, int hastaIndice, int cantidad) {
    
    char *impr = malloc(sizeof(char) * 1024 * 1024 * cantidad);
    
    int u;
    for (u=0; u<=hastaIndice; u++) {
        strcpy(impr, "{");
        int y;
        for (y=0;y<cantidad; y++) {
            strcat(impr, "[");
            char *buff = imprimirNodoMatriz(&matriz[u][y]);
            strcat(impr, buff);
            free(buff);
            if (y==cantidad-1) {
                strcat(impr, "]");
            } else {
                strcat(impr, "],");
            }
        }
        if (u==hastaIndice) {
            strcat(impr, "}");
        } else {
            strcat(impr, "}\n");
        }
    }
    
    return impr;
    
}


char *imprimirNodoMatriz(struct NODO_MATRIZ *nodo) {
    char *impr = malloc(sizeof(char) * 1024);
    sprintf(impr, "accion:%i,nodo:%i,tam:%lld", nodo->accion, nodo->idNodo, nodo->tamanio);
    return impr;
}